package 链表.两数相加;
/**
 * 题目描述：
 * 给你两个非空的链表，表示两个非负的整数。
 * 它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[7,0,8]
 * 解释：342 + 465 = 807.
 * 力扣地址：https://leetcode-cn.com/problems/add-two-numbers/
 * 力扣题：2
 * */
/**
 * 解题思路：
 * 使用迭代的方法
 * 存入两个链表，并初始化进位为0
 * 创建一个链表，并初始化指针为pre
 * 循环比较两个链表，将值取出来
 * 然后/10看看是不是要进位
 * %10获取这个链表的值
 *
 * */

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while(l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;

            carry = sum / 10;
            sum = sum % 10;
            // 创建一个新的结点存储当前位的计算结果
            cur.next = new ListNode(sum);
            // 将指针移动到新创建的结点上
            cur = cur.next;
            // 移动指针
            if(l1 != null)
                l1 = l1.next;
            if(l2 != null)
                l2 = l2.next;
        }
        // 如果carry为1的话说明要进位
        if(carry == 1) {
            // 例如计算 99 + 1 = 100：
            //链表表示为 [9,9] + [1]
            //计算过程：9+1=10（进位1），9+0+1=10（进位1），最后还剩进位1
            //最终结果需要4位数：[0,0,1] 表示100
            //这个最后的进位1就需要通过这段代码添加到链表末尾
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }
}